package com.zxy.javaarithmetic.LinearList;

import com.zxy.javaarithmetic.Utils;

/**
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.sort
 *  @文件名:   QuickSort
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/25 14:25
 *  @描述：    快速排序法
 * 			  1、选择分区点的值（可以简单选择最左侧的值）
 * 			  2、小于分区值的排左侧，大于分区值的排右侧，分区点放中间
 * 			  3、分别对分区点左右两侧的数组再重新排序
 *
 * 			  最好、平均时间复杂度O(nlogn),最坏时间复杂度O(n^2)
 * 			  原地排序、不是稳定排序
 */
public class QuickSort {

	public static void main(String[] args) {
		int[] arr = {6, 1, 2, 6, 9, 3, 4, 6, 10, 8};
		Utils.print(arr, 0, arr.length - 1);
		quickSort(arr, 0, arr.length - 1);
		Utils.print(arr, 0, arr.length - 1);
	}

	private static void quickSort(int[] arr, int left, int right) {
		if (arr == null || arr.length == 0 || left >= right) {
			return;
		}

		int k = partition(arr,left,right);

		//如果出现 666 这样的数据，递归就永远不会结束
		//		quickSort(arr, left, k-1);
		//		quickSort(arr, k, right);
		quickSort(arr, left, k - 1);
		quickSort(arr, k + 1, right);
	}


	/**
	 * 获取分区点，这里简单选择最左侧的点作为分区点，为降低极端情况出现的几率，分区点可以采用：
	 *  1：三数取中（五数取中，七数取中等）
	 *  2：随机数
	 * @return 分区点的下标
	 */
	private static int partition(int[] arr,int l,int r){
		int middle = arr[l];
		int k = l;

		//l,r相遇的点就是分区点的位置
		while(l != r){
			//为什么要从右侧开始移动
			//原因就在于l,r最终会相遇，相遇的点就是分区点，如果是从左侧开始移动，那么最终相遇点的值会大于分区值
			//而我们最后一步是将分区点的值和相遇点的值互换，这时候数据顺序就错了
			while(r > l && arr[r] > middle){
				r--;
			}

			//移动左侧
			while(l < r && arr[l] <= middle){
				l++;
			}

			if(r > l){
				int tmp = arr[l];
				arr[l] = arr[r];
				arr[r] = tmp;
			}
		}
		arr[k] = arr[l];
		arr[l] = middle;

		return l;
	}

}
